package org.example.oneQuestionPerDay;

import java.util.*;

/**
 * 2789. 合并后数组中的最大元素(中等难度)
 * 给你一个下标从 0 开始、由正整数组成的数组 nums 。
 * 你可以在数组上执行下述操作 任意 次：
 * 选中一个同时满足 0 <= i < nums.length - 1 和 nums[i] <= nums[i + 1] 的整数 i 。将元素 nums[i + 1] 替换为 nums[i] + nums[i + 1] ，并从数组中删除元素 nums[i] 。
 * 返回你可以从最终数组中获得的 最大 元素的值。
 *
 * 示例 1：
 *
 * 输入：nums = [2,3,7,9,3]
 * 输出：21
 * 解释：我们可以在数组上执行下述操作：
 * - 选中 i = 0 ，得到数组 nums = [5,7,9,3] 。
 * - 选中 i = 1 ，得到数组 nums = [5,16,3] 。
 * - 选中 i = 0 ，得到数组 nums = [21,3] 。
 * 最终数组中的最大元素是 21 。可以证明我们无法获得更大的元素。
 * 示例 2：
 *
 * 输入：nums = [5,3,3]
 * 输出：11
 * 解释：我们可以在数组上执行下述操作：
 * - 选中 i = 1 ，得到数组 nums = [5,6] 。
 * - 选中 i = 0 ，得到数组 nums = [11] 。
 * 最终数组中只有一个元素，即 11 。
 *
 *
 * 提示：
 *
 * 1 <= nums.length <= 105
 * 1 <= nums[i] <= 106
 * @author: daiziru
 * @createDate: 2024/3/14 9:13
 */
public class P2789 {
    public static void main(String[] args) {
        //输入数组
        System.out.println("请输入几个数并用逗号隔开：");
        Scanner sc = new Scanner(System.in);
        String str = sc.next().toString();
        String[] arr  = str.split(",");
        int[] b = new int[arr.length];
        for(int j = 0; j< b.length;j++) {
            b[j] = Integer.parseInt(arr[j]);
            System.out.println(b[j]+" ");
        }
        //开始执行方法
        long maxNum1 = getMaxNumberMethod1(b);
        System.out.println(maxNum1);
        System.err.println("=======================================");
        long l = maxArrayValue(b);
        System.out.println(l);


    }

    /**
     * 经典，从右往左遍历，找到num[i] <= num[i+1]的两个元素， num[i+1] = num[i+1] + num[i],然后在list中删除num[i]
     * @param nums
     * @return
     */
    private static long getMaxNumberMethod1(int[] nums) {
        long ans = 0;
        List<Long> list = new LinkedList<>();
        for(int num: nums) {
            list.add((long)num);
        }
        //从左到右遍历
        for(int i = nums.length - 1; i >= 0; i--) {
            if(i > 0 && list.get(i - 1) <= list.get(i)) {
                list.set(i, list.get(i - 1) + list.get(i));
                //删除i
                list.remove(i -1);
            }
        }
        return Math.max(ans, list.get(0));
    }

    /**
     * 贪心算法，从右边开始，sum = num[length -1], 如果num[i] < sum, sum = sum + num[i],否则sum = num[i]
     * @param nums
     * @return
     */
    public static long maxArrayValue(int[] nums) {
        long sum = nums[nums.length - 1];
        for (int i = nums.length - 2; i >= 0; i--) {
            sum = nums[i] <= sum ? nums[i] + sum : nums[i];
        }
        return sum;
    }
}
